const common = require('./base/common');
const TreeBuilder = require('./dataStruct/treeBuiler').TreeBuilder;

/**
 * 观远数据一面算法题(2021/3/4)：判断一个二叉树是否是镜像对称的，例如：
 *                  a
 *                /   \
 *               b     b
 *              / \   / \
 *             c  d  d   c
 * 上面这个二叉树就是一个镜像对称的二叉树
 * 
 * @param {*} root 树根节点
 */
let mirrorTree = function(root) {
    if(root == null) {
        return true;
    }

    function judge(values) {
        for(let i=0, len = values.length >>> 1; i < len; ++i) {
            if(values[i] != values[values.length - i - 1]) {
                return false;
            }
        }
        return true;
    }

    let queue = [root];
    while(queue.length) {
        if(!judge(queue.map(x => x == null? x: x.val))) {
            return false;
        }

        queue = queue.reduce((a, b) => b == null? a: a.concat([b.lchild, b.rchild]), []);
    }

    return true;
}

common.testing([
    TreeBuilder.build([5,2,2,3,4,4,3,6,null,null,null,null,null,null,6]),
    TreeBuilder.build([5,2,2,3,4,4,3,9,null,null,null,null,null,null,6]),
    TreeBuilder.build([5,2,2,3,4,4,3,9]),
    TreeBuilder.build([5,2,2,3,4,4,3,9,12,null,null,null,null,null,6]),
    null,
    TreeBuilder.build([5])
], [true, false, false, false, true, true])(root => mirrorTree(root));